package leecode;

import java.util.Arrays;

/**
 * @Classname
 * @Description TODO
 * @Date 2021/8/4 16:33
 * @Created by Alberthch
 * 题目：有效三角形的个数
 */
class Solution_611 {
    // 穷举法，T(n) = O(n^3),超出时间限制
    public static int triangleNumber_1(int[] nums) {
        int n = nums.length;
        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    if (isTriangle(nums[i],nums[j],nums[k])) {
                        num++;
                    }

                }

            }
        }

        return num;

    }

    public static boolean isTriangle(int i, int j, int k) {
        if (i+j>k && i+k>j && k+j>i) {
            return true;
        }
        return false;
    }

    // 排序+二分查找,T(n) = O(n^2lgn)
    public static int triangleNumber_2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // 二分查找的范围：nums[j+1]到nums[n-1]
                // k表示大于两元素和的位置，设置k是为了二分查找失败时
                int left = j + 1, right = n - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;

    }

    // 排序+双指针，T(n) = O(n^2)
    public static int triangleNumber_3(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = i;
            for (int j = i + 1; j < n; ++j) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
                    ++k;
                }
                ans += Math.max(k - j, 0);
            }
        }
        return ans;

    }




        public static void main(String[] args) {
        int[] arr = new int[]{2,2,3,4};
        System.out.println(triangleNumber_1(arr));
        System.out.println(triangleNumber_2(arr));

    }
}
